package com.zjj.algorithm.learning.leetcode.linkedlist;

/**
 * 328. 奇偶链表 中档题
 * 给定单链表的头节点 head ，将所有索引为奇数的节点和索引为偶数的节点分别组合在一起，然后返回重新排序的列表。
 * <p>
 * 第一个节点的索引被认为是 奇数 ， 第二个节点的索引为 偶数 ，以此类推。
 * <p>
 * 请注意，偶数组和奇数组内部的相对顺序应该与输入时保持一致。
 * <p>
 * 你必须在 O(1) 的额外空间复杂度和 O(n) 的时间复杂度下解决这个问题。
 * <p>
 * <p>
 * 输入: head = [1,2,3,4,5]
 * 输出: [1,3,5,2,4]
 * <p>
 * 输入: head = [2,1,3,5,6,4,7]
 * 输出: [2,3,6,7,1,5,4]
 * 提示:
 * <p>
 * n ==  链表中的节点数
 * 0 <= n <= 104
 * -106 <= Node.val <= 106
 *
 * @author zjj_admin
 * @date 2022/12/20 14:33
 */
public class OddEvenLinkedList {

    public static void main(String[] args) {

        ListNode node4 = new ListNode(6, null);
        ListNode node5 = new ListNode(5, node4);
        ListNode node6 = new ListNode(4, node5);
        ListNode node7 = new ListNode(3, node6);
        ListNode node8 = new ListNode(2, node7);
        ListNode node9 = new ListNode(1, node8);

        ListNode res = oddEvenList(node9);
        System.out.println("res = " + res);

    }


    /**
     * 时间
     * 0 ms
     * 击败
     * 100%
     * 内存
     * 41.2 MB
     * 击败
     * 30.6%
     *
     * @param head
     * @return
     */
    public static ListNode oddEvenList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        // head 为奇链表头结点，o 为奇链表尾节点
        ListNode o = head;
        // p 为偶链表头结点
        ListNode p = head.next;
        // e 为偶链表尾节点
        ListNode e = p;
        while (o.next != null && e.next != null) {
            o.next = e.next;
            o = o.next;
            e.next = o.next;
            e = e.next;
        }
        o.next = p;
        return head;
    }

}
